package com.duoduo.树;

import com.duoduo.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @program: algorithm
 * @description: 对称二叉树101
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * @author: chaidl  ！
 * @create: 2022-04-14 15:27
 */
public class 对称二叉树101 {
	//采用迭代的方式
	public boolean isSymmetric2(TreeNode root) {
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		TreeNode left=root.left;
		TreeNode right=root.right;
		if (root==null || (left == null && right == null)){
			return true;
		}
		queue.add(left);
		queue.add(right);
		//把左右两个节点放入队列中
		while (!queue.isEmpty()){
			left=queue.poll();
			right=queue.poll();
			//如果左右节点都为空，表示是相同的
			if (left==null && right==null){
				continue;
			}
			if ((left == null || right == null)  || (left.val!=right.val)){
				return false;
			}
		//	到这里表示还是对称的，需要继续判断，所以就将他们的子节点放进去
			queue.add(left.left);
			queue.add(right.right);
			queue.add(left.right);
			queue.add(right.left);
		}
		return true;
	}
	
	//第一次采用递归的方法
	public boolean isSymmetric(TreeNode root) {
		if (root==null){
			return true;
		}
		return dfs(root.left,root.right);
	}
	
	private boolean dfs(TreeNode left,TreeNode right) {
		if (left==null && right == null){
			return true;
		}
		if (left==null || right == null || left.val!=right.val){
			return false;
		}
		return dfs(left.left,right.right) && dfs(left.right,right.left);
	}
}
